import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1637. 两点之间不包含任何点的最宽垂直面积
 * https://leetcode-cn.com/problems/widest-vertical-area-between-two-points-containing-no-points/
 */
public class Solutions_1637 {
    public static void main(String[] args) {
        int[][] points1 = {{8, 7}, {9, 9}, {7, 4}, {9, 7}};  // output: 1
        int[][] points2 = {{3, 1}, {9, 0}, {1, 0}, {1, 4}, {5, 3}, {8, 8}};  // output: 3

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(points1);
        inputs.add(points2);

        for (int[][] input : inputs) {
            int result = maxWidthOfVerticalArea(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：排序
     * 排序后，相邻元素之间进行比较，得到最大的差值
     */
    public static int maxWidthOfVerticalArea(int[][] points) {
        // 将 x 轴坐标加入到一维数组后，单独对一维数组排序
        int len = points.length;
        int[] xArr = new int[len];
        for (int i = 0; i < len; i++) {
            xArr[i] = points[i][0];
        }
        Arrays.sort(xArr);
        int res = 0;
        for (int i = 1; i < xArr.length; i++) {
            int cur = xArr[i] - xArr[i - 1];
            if (cur > res) {
                res = cur;
            }
        }
        return res;
    }
}
